The present invention relates to a method of queuing data packets. More particularly, but not exclusively, the present invention relates to a method of queuing data packets where the data packets comprise packets of both a first and a second type.
In computer networks data packets are frequently queued before onwards transmission in order to prevent network links from being overloaded. For instance, at a network router packets must be queued until there is available credit on an onwards network link to allow a packet to be transmitted. In conventional computer networks it is known to have different packet types with differing requirements for queuing. In particular, it is known to have two different packet types where a first packet type is of a relatively higher priority for onwards transmission.
In such a computer network a bypass capable queue may be implemented for queuing unpredictable sequences of two distinct packet types. Packets of the first type must be transmitted from the queue in order, but may overtake packets of the second type if credit for the second type is not available. Packets of the second type must also be transmitted from the queue in order, but may not overtake packets of the first type.
Before either packet type can be transmitted sufficient credit for that packet must be available on the onwards network link. A packet may only be transmitted if the router or other network element identifies that sufficient credit for that packet type is available.
It is known to implement a bypass capable queue by providing a single queue of data packets with links between packets within the queue of the same packet type, and between packet types. The links may take the form of two pointers stored alongside each packet pointing to the next packet within the queue of the same packet type, and a group of packets of the other type. When a packet is scheduled for transmission the pointers must be individually updated. This is a particularly complex process when a packet of the first packet type which is the last packet in a group of type 1 packets overtakes a packet of the second packet type. Furthermore, as well as the pointer arithmetic being computationally expensive each time a packet is transmitted, the process is also prone to errors. If a fault causes a pointer to become corrupted then it can be difficult to re-establish the bypass capable queue. Known bypass capable queues based upon pointers to the next packet of a given packet type require significant processing each time a packet is transmitted.
An alternative approach to implementing a bypass capable queue is to store each received packet with a time stamp and an indication of the type of packet. When determining which packet to transmit, the packet timestamps and packet types for packets can be compared to determine the relative order packets arrived in and where packets of each packet type appear within the queue. Again this known approach is computationally expensive. A further problem of time stamping is that tracking the relative order of timestamps can become complex when the timestamp wraps around (for instance, from 99 to 0).
It is known to implement a bypass capable queue with separate queues for each packet type. However, in such a known bypass capable queue, time stamping or some alternative form of linkage between the separate packet queues is still required to preserve the relative packet ordering.